package chapter03_binaryTree;

/**
 * 描述：
 *      判断t1树是否包含t2树的全部拓扑结构
 *      思路：遍历t1知道某个结点的值与t2的头结点相同，则检查以该结点为头的子树是否能与t2匹配
 *      检查过程让t1的当前结点随着t2移动，如果遇到t1为空或者两个结点不相等，则匹配失败
 * @author hl
 * @date 2021/5/28 10:15
 */
public class ContainsTopo {
    public static void main(String[] args) {
        SerialBinaryTree serial = new SerialBinaryTree();
        Node t1 = serial.reconByLevel("1!2!3!4!5!6!7!8!9!10!#!#!#!#!#!#!#!#!#!#!#!");
        Node t2 = serial.reconByLevel("2!4!5!8!10!#!#!#!#!#!#!");
        ContainsTopo containsTopo = new ContainsTopo();
        boolean contains = containsTopo.contains(t1, t2);
        System.out.println(contains);
    }

    public boolean contains(Node t1, Node t2){
        if (t1 == null) {
            return false;
        }
        return check(t1, t2) || contains(t1.left, t2) || contains(t1.right, t2);
    }

    private boolean check(Node h, Node t2) {
        if (t2 == null) {
            return true;
        }
        if (h == null || h.val != t2.val) {
            return false;
        }
        return check(h.left, t2.left) && check(h.right, t2.right);
    }
}
